class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val 
        self.left=left 
        self.right=right 

from collections import deque
def build_level(lst):
    head=TreeNode(lst[0])
    que=deque([head])
    i=1
    while len(que)>0 and i<len(lst):
        cur=que.popleft()
        if lst[i]:
            cur.left=TreeNode(lst[i])
            que.append(cur.left)
        if i+1<len(lst) and lst[i+1]:
            cur.right=TreeNode(lst[i+1])
            que.append(cur.right)
        i+=2
    return head 

# def traversal_level(head):
#     ans=[]
#     que=deque([head])
#     next_k=1
#     while len(que)>0:
#         k,next_k=next_k,0
#         tmp=[]
#         for _ in range(k):
#             cur=que.popleft()
#             tmp.append(cur.val)
#             if cur.left:
#                 que.append(cur.left)
#                 next_k+=1
#             if cur.right:
#                 que.append(cur.right)
#                 next_k+=1
#         ans.append(tmp)
#     return ans 

# head=build_level([3,9,20,None,None,15,7])
# print(traversal_level(head))

#**************
# def dfs(root,pre):
#     if not root: return True #**
#     if not dfs(root.left,pre) or root.val<=pre: return False 
#     pre=root.val 
#     return dfs(root.right,pre)

# def solve(root):
#     return dfs(root,-float('inf'))

# root=build_level([2,1,3])
# print(solve(root))
# root=build_level([5,1,4,None,None,3,6])
# print(solve(root))

#*******************



def solve(root,targetSum):
    ans=0
    mp={0:1}
    def dfs(root,pre,mp,target):
        if not root: return
        nonlocal ans
        pre+=root.val 
        if pre-target in mp: ans+=mp[pre-target]
        if pre in mp: mp[pre]+=1
        else: mp[pre]=1
        dfs(root.left,pre,mp,target)
        dfs(root.right,pre,mp,target)
        mp[pre]-=1
    dfs(root,0,mp,targetSum)
    return ans

root=build_level([10,5,-3,3,2,None,11,3,-2,None,1])
print(solve(root,8))
